\documentclass{ctexart}
\usepackage{graphicx} %插入图片的宏包
\usepackage{diagbox}
\usepackage{float} %设置图片浮动位置的宏包
\usepackage{subfigure}
\usepackage{amsmath}
\title{Numerical Analysis Ex3}
\date{4-11-2022}
\author{王惠恒 3200300395}
\usepackage{geometry}
 \geometry{
 a4paper,
 total={170mm,257mm},
 left=20mm,
 top=5mm,
 }
\begin{document}
\maketitle
\textbf{I}:Given that $s \in S_{3}^{2}$ on $[0,2]$,and $p(x) \in P_3$
$s(x)=\left\{
	\begin{aligned}
	p(x) \quad ,x \in [0,1]\\
	(2-x)^3 \quad ,x \in [1,2]\\
	\end{aligned}
	\right.$
 .Then we let the general equation of $p(x)$ be $p(x)=ax^3+bx^2+cx+d$,and we can easily calculate the first derivative and second derivative of $s(x)$.
 $$s(x)=\left\{
	\begin{aligned}
	ax^3+bx^2+cx+d \quad ,x \in [0,1]\\
	(2-x)^3 \quad ,x \in [1,2]\\
	\end{aligned}
	\right.
    s'(x)=\left\{
	\begin{aligned}
	3ax^2+2bx+c \quad ,x \in [0,1]\\
	(2-x)^3 \quad ,x \in [1,2]\\
	\end{aligned}
	\right.
    s''(x)=\left\{
	\begin{aligned}
	6ax+2b \quad ,x \in [0,1]\\
	(2-x)^3 \quad ,x \in [1,2]\\
	\end{aligned}
	\right.$$
 (1):$s(0)=p(0)=0 \Rightarrow d=0$\\
 (2):$s(1)=p(1)=1 \Rightarrow a+b+c=1$\\
 (3):$s'(1)=p'(1)=-3 \Rightarrow 3a+2b+c=-3$\\
 (4):$s''(1)=p''(1)=6 \Rightarrow 6a+2b=6$\\
By solving (1),(2),(3),(4),we can have $a=7,b=-18,c=12,d=0$,which means that $p(x)=7x^3-18x^2+12x$. As $s''(0)=-36 \neq 0,s''(2)=48 \neq 0$, thus, $s(x)$ is not a natural cubic spline.\\

\textbf{II}:(a)Given that there are $n$ of knots and $s \in S_{2}^{1}$ which is (n+1) dimension of linear space.From the given condition $f_i=f(x_i)$ provides $n$ of equations and an additional condition is needed to determine s uniquely.\\
(b)Given that $m_i=s'(x_i),p_i=s|_{[x_i,x_{i=1}]},f_i=f(x_i)$,by hermite interpolation, we know that 
\begin{align*}
    p_i(x)&=f(x_i)+f'(x_i)(x-x_i)+f[x_i,x_i,x_{i+1}](x-x_i)^2\\
    p_i(x)&=f(x_i)+m_i(x-x_i)+\frac{\frac{f(x_{i+1})-f(x_i)}{x_{i+1}-x_i}-m_i}{x_{i+1}-x_i}(x-x_i)^2\\
    p_i&=f_i+m_i(x-x_i)+\frac{f_{i+1}-f_i-m_i(x_{i+1}-x_i)}{(x_{i+1}-x_i)^2}(x-x_i)^2\\
\end{align*}
(c)Given that $m_1=f'(a)$,and we know that $m_{i+1}=p_i'(x_{i+1})$.Use the result in (b),calculate the first derivative of $p_i'(x)$.
\begin{align*}
    p_i'(x)&=m_i+2 \cdot \frac{f_{i+1}-f_i-m_i(x_{i+1}-x_i)}{(x_{i+1}-x_i)^2}(x-x_i)\\
    p_i'(x_{i+1})&=m_i+2 \cdot (\frac{f_{i+1}-f_i-m_i(x_{i+1}-x_i)}{x_{i+1}-x_i})\\
     m_{i+1}&=m_i+2 \cdot (\frac{f_{i+1}-f_i-m_i(x_{i+1}-x_i)}{x_{i+1}-x_i})
\end{align*}
for $i=1,2,...,n-1$.
\\

\textbf{III}:Given that $s_{1}(x)=1+c(x+1)^3 , x \in [-1,0] , c \in R$.As $s(x)$ is a natural cubic spline,the we let $s(x)$ as below and then calculate its first derivative and second derivative.
$$s(x)=\left\{
	\begin{aligned}
	s_1(x)&=1+c(x+1)^3 \quad ,x \in [-1,0]\\
	s_2(x)&=a_0x^3+a_1x^2+a_2x+a_3 \quad ,x \in [0,1]\\
	\end{aligned}
	\right.$$
$$s'(x)=\left\{
	\begin{aligned}
	s_1(x)&=3c(x+1)^2 \quad ,x \in [-1,0]\\
	s_2(x)&=3a_0x^2+2a_1x+a_2 \quad ,x \in [0,1]\\
	\end{aligned}
	\right.$$
 $$s''(x)=\left\{
	\begin{aligned}
	s_1(x)&=6c(x+1) \quad ,x \in [-1,0]\\
	s_2(x)&=6a_0x+2a_1 \quad ,x \in [0,1]\\
	\end{aligned}
	\right.
 $$
 (1):$s(0)=1+c=a_3$\\
 (2):$s'(0)=3c=a_2$\\
 (3):$s''(0)=6c=2a_1$\\
 (4):$s''(1)=0 \Rightarrow a_1=-3a_0$\\
 (5):$s(1)=-1 \Rightarrow 6c+1=-1$\\
 By solving (1),(2),(3),(4),(5),we can have $a_0=\frac{1}{3},a_1=-1,a_2=-1,a_3=\frac{2}{3},c=-\frac{1}{3}$.\\Thus,$s_2(x)=\frac{1}{3}x^3-x^2-x+\frac{2}{3}$\\

 \textbf{IV}:(a)Given that $f(x)=cos(\frac{\pi}{2}x),x \in [-1,1]$.Let the natural cubic spline be $s(x)=s(f;x)$,the knots are $x_1=-1,x_2=0,x_3=1$.
 $$s(x)=\left\{
	\begin{aligned}
	s_1(x)&=a_1x^3+b_1x^2+c_1x+d_1 \quad ,x \in [-1,0]\\
	s_2(x)&=a_2x^3+b_2x^2+c_2x+d_2 \quad ,x \in [0,1]\\
	\end{aligned}
	\right.$$
  $$s'(x)=\left\{
	\begin{aligned}
	s_1(x)&=3a_1x^2+2b_1x+c_1 \quad ,x \in [-1,0]\\
	s_2(x)&=3a_2x^2+2b_2x+c_2 \quad ,x \in [0,1]\\
	\end{aligned}
	\right.$$
  $$s''(x)=\left\{
	\begin{aligned}
	s_1(x)&=6a_1x+2b_1 \quad ,x \in [-1,0]\\
	s_2(x)&=6a_2x+2b_2 \quad ,x \in [0,1]\\
	\end{aligned}
	\right.$$
 As it is a natural cubic spline, $s''(-1)=s''(1)=0 \Rightarrow M_1=0,M_3=0$,where $M_i=s''(f;x_i)$.Now we note that a difference table and some general expressions that take part in calculation.
 \begin{align*}
       \mu_i&=\frac{x_i-x_{i-1}}{x_{i+1}-x_{i-1}}\\
       \lambda_i&=\frac{x_{i+1}-x_{i}}{x_{i+1}-x_{i-1}}\\
       \mu_iM_{i-1}+2M_i+\lambda_iM_{i+1}&=6f[x_{i-1},x_i,x_{i+1}]\\
       s'(x_i)&=f[x_i,x_{i+1}]-\frac{1}{6}(M_{i+1}+2M_i)(x_{i+1}-x_i)\\
       s'(x_i)&=f[x_{i-1},x_{i}]-\frac{1}{6}(M_{i-1}+2M_i)(x_{i-1}-x_i)
 \end{align*}
 \begin{table}[!htbp]
    \centering
    \begin{tabular}{|c|c|c|c|}
    \hline
    $x_1=-1$&$0$&-&-\\
    \hline
    $x_2=0$&$1$&$1$&-\\
    \hline 
    $x_3=1$&$0$&$-1$&$-1$\\
    \hline
    \end{tabular}
\end{table}

Now when $i=2 \Rightarrow \mu_2=\frac{1}{2},\lambda_2=\frac{1}{2},M_2=-3$\\
(1):$s'(-1)=3a_1-2b_1+c_1=\frac{3}{2}$\\
(2):$s'(0)=c_1=c_2=0$\\
(3):$s'(1)=3a_2+2b_2+c_2=-\frac{3}{2}$\\
(4):$s''(-1)=-6a_1+2b_1=0$\\
(5):$s''(1)=6a_2+2b_2=0$\\
(6):$s(0)=d_1=d_2$\\
(7):$s(1)=s(-1)=\frac{1}{2}-\frac{3}{2}+d_1=0$\\
By solving the equations stated above,we can have $a_1=-\frac{1}{2},b_1=-\frac{3}{2},c_1=0.d_1=1,a_2=\frac{1}{2},b_2=-\frac{3}{2},c_2=0,d_2=1$,then the natural cubic spline is 
$$s(x)=\left\{
	\begin{aligned}
	s_1(x)&=-\frac{1}{2}x^3-\frac{3}{2}x^2+1 \quad ,x \in [-1,0]\\
	s_2(x)&=\frac{1}{2}x^3-\frac{3}{2}x^2+1 \quad ,x \in [0,1]\\
	\end{aligned}
	\right.$$
(b)Now we verify the minimal total bending energy:\\
(i)$g(x)=(x+1)-x(x+1)=1-x^2,g''(x)=-2,\int_{-1}^{1} (-2)^2 dx=8$\\
 $$s''(x)=\left\{
	\begin{aligned}
	s_1(x)&=-3x-3 \quad ,x \in [-1,0]\\
	s_2(x)&=3x-3 \quad ,x \in [0,1]\\
	\end{aligned}
	\right.$$
 $$6=\int_{-1}^{1}[s''(x)]^2 dx \leq \int_{-1}^{1} (-2)^2 dx =8 $$
 (ii)$g(x)=f(x),g''(x)=-\frac{\pi^2}{4}cos(\frac{\pi}{2}x)$
 $$6=\int_{-1}^{1}[s''(x)]^2 dx \leq \int_{-1}^{1} \frac{\pi^4}{16}cos^2(\frac{\pi}{2}x) dx=\frac{\pi^4}{16}$$

 \textbf{V}:(a)As the lecture stated, the recursive definition of B-splines and the hat function are 
 $$B_{i}^{n+1}(x)=\frac{x-t_{i-1}}{t_{i+n}-t_{i-1}}B_{i}^{n}(x)+\frac{t_{i+n+1}-x}{t_{i+n+1}-t_{i}}B_{i+1}^{n}(x)$$
 $$B_i^1= \hat{B}_i=\left\{
	\begin{aligned}
	\frac{x-t_{i-1}}{t_i-t_{i-1}} \quad ,x \in (t_{i-1},t_i]\\
	\frac{t_{i+1}-x}{t_{i+1}-t_i} \quad ,x \in (t_i,t_{i+1}]\\
    0 \quad ,otherwise
	\end{aligned}
	\right.$$
 We have $B_i^2=\frac{x-t_{i-1}}{t_{i+1}-t_{i-1}}\hat{B}_i+\frac{t_{i+2}-x}{t_{i+2}-t_i}\hat{B}_{i+1}$
\begin{align*}
    B_i^2=\left\{
	\begin{aligned}
	\frac{x-t_{i-1}}{t_{i+1}-t_{i-1}} \cdot \frac{x-t_{i-1}}{t_i-t_{i-1}} \quad ,x \in (t_{i-1},t_i]\\
	\frac{x-t_{i-1}}{t_{i+1}-t_{i-1}}B_{i}^{1}(x)+\frac{t_{i+2}-x}{t_{i+2}-t_{i}}B_{i+1}^{1}(x) \quad ,x \in (t_i,t_{i+1}]\\
    0 \quad ,otherwise
	\end{aligned}
	\right.
 \end{align*}
 \begin{align*}
     B_i^2(x)=\left\{
	\begin{aligned}
	\frac{(x-t_{i-1})^2}{(t_{i+1}-t_{i-1})(t_i-t_{i-1})} \quad ,x \in (t_{i-1},t_i]\\
	\frac{(x-t_{i-1})(t_{i+1}-x)}{(t_{i+1}-t_{i-1})(t_{i+1}-t_i)}+\frac{(t_{i+2}-x)(x-t_i)}{(t_{i+2}-t_{i})(t_{i+1}-t_i)} \quad ,x \in (t_i,t_{i+1}]\\
    \frac{(t_{i+2}-x)^2}{(t_{i+2}-t_i)(t_{i+2}-t_{i+1})} \quad ,x \in (t_{i+1},t_{i+2}]\\
    0 \quad ,otherwise
	\end{aligned}
	\right.
\end{align*}
(b)\begin{align*}
     \frac{d}{dx}B_i^2(x)=\left\{
	\begin{aligned}
	\frac{2(x-t_{i-1})}{(t_{i+1}-t_{i-1})(t_i-t_{i-1})} \quad ,x \in (t_{i-1},t_i]\\
	\frac{t_{i+1}+t_{i-1}-2x}{(t_{i+1}-t_{i-1})(t_{i+1}-t_i)}+\frac{t_{i+2}+t_i-2x}{(t_{i+2}-t_{i})(t_{i+1}-t_i)} \quad ,x \in (t_i,t_{i+1}]\\
    \frac{2(t_{i+2}-x)}{(t_{i+2}-t_i)(t_{i+2}-t_{i+1})} \quad ,x \in (t_{i+1},t_{i+2}]\\
    0 \quad ,otherwise
	\end{aligned}
	\right.
\end{align*}
\begin{align*}
    \frac{d}{dx}B_i^2(t_i)&=\frac{2}{t_{i+1}-t_{i-1}}\\
    \lim \limits _{{x} \to {t_i^+}}B_i^2(x)&=\frac{2}{t_{i+1}-t_{i-1}}+0=\lim \limits _{{x} \to {t_i^-}}B_i^2=\frac{d}{dx}B_i^2(t_i)\\
    \frac{d}{dx}B_i^2(t_{i+1})&=\frac{t_{i+2}-t_{i+1}}{t_{i+2}-t_{i}}\\
    \lim \limits _{{x} \to {t_{i+1}^+}}B_i^2(x)&=\frac{t_{i+2}-t_{i+1}}{t_{i+1}-t_{i}}= \lim \limits _{{x} \to {t_{i+1}^-}}B_i^2(x)=\frac{d}{dx}B_i^2(t_{i+1})\\
\end{align*}
Then we proved the continuity of $\frac{d}{dx}B_i^2(x)$ at the points $t_i$ and $t_{i+1}$。

(c)$\forall x \in(t_{i-1},t_{i}],\frac{d}{dx}B_i^2>0$ and $\forall x \in (t_i,t_{i+1}],\frac{d}{dx}B_i^2(x)<0$,and also  by the property of the continuity proved in (b),$\exists ! x^{*} \in (t_{i-1},t_{i+1})$ such that $\frac{d}{dx}B_i^2(x^{x})=0$.The expression of $x^{*}$ is $x^{*}=\frac{t_{i+2}t_{i+1}-t_it_{i-1}}{t_{i+2}+t_{i+1}-t_i-t_{i-1}}$

(d)Consider the possibility of attaining the maximum and minimum points which are the points on the bound and the extreme point.$B_i^2(t_{i+2})=0,B_i^2(x^{*})<1$,then we have $B_i^2(x) \in  [0,1)$

(e)For $t_i=i$,
\begin{align*}
    B_{i,Z}^2(x)=\left\{
	\begin{aligned}
	\frac{(x-i+1)^2}{2} \quad ,x \in (i-1,i]\\
	\frac{3}{4}-(x-(i+\frac{1}{2}))^2 \quad ,x \in (i,i+1]\\
    \frac{(i+2-x)^2}{2} \quad ,x \in (i+1,i+2]\\
    0 \quad ,otherwise
	\end{aligned}
	\right.
 \end{align*}
The graph is shown below green in colour:
\begin{figure}[H]
\includegraphics[width=0.5\textwidth]{NApic1.jpeg}
\end{figure}

\textbf{VI}:Theorem 3.32,case n=2:
\begin{align*}
    B_i^2&=(t_{i+2}-t_{i-1})[t_{i-1},t_i,t_{i+1},t_{i+2}](t-x)_{+}^2\\
    &=[t_{i},t_{i+1},t_{i+2}](t-x)_{+}^2-[t_{i-1},t_{i},t_{i+1}](t-x)_{+}^2\\
    &=\frac{[t_{i+1},t_{i+2}](t-x)_{+}^2-[t_{i},t_{i+1}](t-x)_{+}^2}{t_{i+2}-t_i}-\frac{[t_{i},t_{i+1}](t-x)_{+}^2-[t_{i-1},t_{i}](t-x)_{+}^2}{t_{i+1}-t_{i-1}}\\
    &=\frac{\frac{(t_{i+2}-x)_{+}^2-(t_{i+1}-x)_{+}^2}{t_{i+2}-t_{i+1}}-\frac{(t_{i+1}-x)_{+}^2-(t_{i}-x)_{+}^2}{t_{i+1}-t_{i}}}{t_{i+2}-t_{i}}-\frac{\frac{(t_{i+1}-x)_{+}^2-(t_{i}-x)_{+}^2}{t_{i+1}-t_{i}}-\frac{(t_{i}-x)_{+}^2-(t_{i-1}-x)_{+}^2}{t_{i}-t_{i-1}}}{t_{i+1}-t_{i-1}}\\
    &=\left\{
	\begin{aligned}
	\frac{(x-t_{i-1})^2}{(t_{i+1}-t_{i-1})(t_i-t_{i-1})} \quad ,x \in (t_{i-1},t_i]\\
	\frac{(x-t_{i-1})(t_{i+1}-x)}{(t_{i+1}-t_{i-1})(t_{i+1}-t_i)}+\frac{(t_{i+2}-x)(x-t_i)}{(t_{i+2}-t_{i})(t_{i+1}-t_i)} \quad ,x \in (t_i,t_{i+1}]\\
    \frac{(t_{i+2}-x)^2}{(t_{i+2}-t_i)(t_{i+2}-t_{i+1})} \quad ,x \in (t_{i+1},t_{i+2}]\\
    0 \quad ,otherwise
	\end{aligned}
	\right.
\end{align*}

\textbf{VII}:This is to prove Corollary 3.33  by Theorem 3.34 through mathematical induction.For the case $n=0$,$\frac{1}{t_i-t_{i-1}}\int_{t_{i-1}}^{t_{i}} B_i^0(t)dt=\frac{1}{t_i-t_{i-1}}\int_{t_{i-1}}^{t_{i}} 1 dt=1$.It is true for the case of $n=0$.Suppose that it is true for $(n-1)$th case:
$$\frac{1}{t_{i+n-1}-t_{i-1}}\int_{t_{i-1}}^{t_{i+n-1}} B_i^{n-1}(x)dx=\frac{1}{n}$$
Consider the $n$th case:
\begin{align*}
    \int_{t_{i-1}}^{t_{i+n}}B_i^n(t)dt&=t \cdot B_i^n(t)|_{t_{i-1}}^{t_{i+n}}-\int_{t_{i-1}}^{t_{i+n}}t\cdot \frac{d}{dt}B_i^n(t)dt\\
    &=-\int_{t_{i-1}}^{t_{i+n}}t\cdot \frac{d}{dt}B_i^n(t)dt\\
    &=n(\frac{1}{t_{i+n}-t_i}\int_{t_i}^{t_{i+n}}tB_{i+1}^{n-1}(t)dt-\frac{1}{t_{i+n-1}-t_{i-1}}\int_{t_{i-1}}^{t_{i+n-1}}tB_{i}^{n-1}(t)dt)--(1)\\
\end{align*}
From the recursive expression of $B_i^{n}$
\begin{align*}
    B_i^n(t)&=\frac{t-t_{i-1}}{t_{i+n-1}-t_{i-1}}B_i^{n-1}(t)+\frac{t_{i+n}-t}{t_{i+n}-t_{i}}B_{i+1}^{n-1}(t)\\
    \int_{t_{i-1}}^{t_{i+n}}B_i^n(t)dt&=\int_{t_i}^{t_{i+n}}\frac{t_{i+n}-t}{t_{i+n}-t_{i}}B_{i+1}^{n-1}(t) dt+\int_{t_{i-1}}^{t_{i+n-1}}\frac{t-t_{i-1}}{t_{i+n-1}-t_{i-1}}B_i^{n-1}(t) dt--(2)\\
\end{align*}
From (1) and (2),we have 
\begin{align*}
    \frac{n+1}{t_{i+n}-t_{i}}\int_{t_i}^{t_{i+n}}tB_{i+1}^{n-1}dt-\frac{n+1}{t_{i+n-1}-t_{i-1}}\int_{t_{i-1}}^{t_{i+n-1}}tB_i^{n-1}dt=\frac{t_{i+n}-t_{i-1}}{n}\\
\end{align*}
Then substitute into (1),we have 
\begin{align*}
    \int_{i-1}^{i+n}B_i^n(t)dt&=\frac{t_{i+n}-t_{i-1}}{n+1}\\
    \frac{1}{t_{i+n}-t_{i-1}}\int_{i-1}^{i+n}B_i^n(t)dt&=\frac{1}{n+1}
\end{align*}
Hence, it is true for the $n$th case.In conclusion,it is universally true for $n \in Z,n \geq 0$.\\

\textbf{VIII}:(a)Given that $m=4,n=2$,the complete symmetric polynomial is in degree 2 and 3 variables.\begin{table}[!htbp]
    \centering
    \begin{tabular}{|c|c|c|c|}
    \hline
    $x_1$&$x_1^4$&-&-\\
    \hline
    $x_2$&$x_2^4$&$x_1^3+x_2^3+x_1^2x_2+x_2^2x_1$&-\\
    \hline 
    $x_3$&$x_3^4$&$x_2^3+x_3^3+x_2^2x_3+x_3^2x_2$&$x_1^2+x_2^2+x_3^2+x_1x_2+x_2x_3+x_1x_2$\\
    \hline
    \end{tabular}
\end{table}
$$\tau_2(x_1,x_2,x_3)=x_1x_2+x_2x_3+x_1x_3+x_1^2+x_2^2+x_3^2$$
Hence,we verified $\tau_2(x_1,x_2,x_3)=[x_1,x_2,x_3]x^4$.\\

(b)By the recursive relation on complete symmetric polynomials,we have 
\begin{align*}
    \tau_{k+1}(x_1,...,x_n,x_{n+1})&=\tau_{k+1}(x1,...,x_n)+x_{n+1}\tau_k(x_1,...,x_n,x_{n+1})\\
    \tau_{k+1}(x_1,...,x_n,x_{n+1})-x_1\tau_k(x1,...,x_n,x_{n+1})&=\tau_{k+1}(x1,...,x_n)+x_{n+1}\tau_k(x_1,...,x_n,x_{n+1})-x_1\tau_k(x1,...,x_n,x_{n+1})\\
    (x_{n+1}-x_1)\tau_k(x_1,...,x_n,x_{n+1})&=\tau_{k+1}(x_2,...,x_n,x_{n+1})-\tau_{k+1}(x_1,...,x_n)\\
    \tau_k(x_1,...,x_n,x_{n+1})&=\frac{\tau_{k+1}(x_2,...,x_n,x_{n+1})-\tau_{k+1}(x_1,...,x_n)}{x_{n+1}-x_1}
\end{align*}
Now we prove by mathematical induction.For the case of $n=0$,$\tau_m(x_i)=[x_i]x^m=x_i^m$.It is true for $n=0$.Suppose that the $(n-1)$th case is true:
$$\tau_{m-n+1}(x_i,...,x_{i+n-1})=[x_i,...,x_{i+n-1}]x^{m} $$
Now we consider the $n(\leq m)$th case:
\begin{align*}
    \tau_{m-n}(x_i,...,x_{i+n})&=\frac{\tau_{m-n+1}(x_{i+1},...,x_{i+n},x_{i+n})-\tau_{m-n+1}(x_i,...,x_{i+n-1})}{x_{i+n}-x_i}\\
    &=\frac{[x_{i+1},...,x_{i+n}]x^m-[x_i,...,x_{i+n-1}]x^m}{x_{i+n}-x_i}\\
    &=[x_i,...,x_{i+n},x_{i+n}]x^m
\end{align*}
Hence,it is true for the $n$th term.In conclusion, it is universally true for $n \leq m$ of the expression.
\end{document}
 